/*
你有一些小球，从左到右依次编号为1,2,3，…，n。
你可以执行两种指令。其中，A X Y表示把小球X移动到小球Y左边，B X Y表示把小球X移动到Y右边。指令保证合法，即X不等于Y。
输入小球个数n，指令条数m和m条指令，从左到右输出最后的序列。注意，n可能高达500000，而m可能高达100000。
样例输入：
6 2
A 1 4
B 3 5
样例输出：
2 1 4 5 3 6
--------------------------------------------------------------------------------
分析：使用链表来完成此题，如果用数组来模拟的话耗时太大。
 */

package com.yuan.algorithms.Algorithm_1;

import java.util.Scanner;

class link{
    /**
     * 小球编号，左边的球，右边的球。
     */
    int i,left,right;
}
public class 链表_移动小球 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();//接收小球个数
            int m = sc.nextInt();//接收指令条数
            link[] arr = new link[n+1];//创建相应的链表
            //初始化链表
            for (int i = 0; i <= n; i++) {
                arr[i] = new link();
            }
            for (int i = 1; i <= n; i++) {
                arr[i].i = i;
                arr[i].left = i-1;
                arr[i].right = i+1;
            }
            arr[n].right = 0;//最后一个小球右边的球不存在，标记为0。
            //接收指令
            for (int i = 0; i < m; i++) {
                char instruct = sc.next().charAt(0);
                int a = sc.nextInt();
                int b = sc.nextInt();
                //数据变化的顺序很重要，不能随意更改
                if (instruct == 'A') {
                    arr[arr[a].right].left = arr[a].left;//更新a球后面一个球的数据(向前移动一位);
                    arr[arr[a].left].right = arr[a].right;//更新a球前一个球的数值
                    arr[a].left = arr[b].left;//改变a左边的数值
                    arr[a].right = b;//改变a右边的数值
                    arr[arr[b].left].right = a;//更新b前一个球的数值
                    arr[b].left = a;//将a移动到b的左边
                    
                } else {
                    arr[arr[a].left].right = arr[a].right;//改变a球前一个球的数值
                    arr[arr[a].right].left = arr[a].left;//改变a球后一个球的数值
                    arr[a].left = b;//改变a球左边的数据
                    arr[arr[b].right].left = a;//改变b球后一个球的数值
                    arr[a].right = arr[b].right;//改变a球右边的数据
                    arr[b].right = a;//改变b球右边的数值
                }
            }
            int tab = 0;//球的编号的起点
            //获取起点
            for (int i = 1; i <= n; i++) {
                if (arr[i].left == 0) {
                    tab = i;
                    break;
                }
            }
            for (int i = 0; i < n; i++) {
                if (i==n-1) {
                    System.out.println(tab);
                }else{
                    System.out.print(tab+" ");
                }
                tab = arr[tab].right;
            }
        }
    }
    
}
